package com.dhu.graph.digraph;

import com.dhu.graph.basic.GraphImpls.DiGraph;
import com.dhu.graph.utils.ArrayQueue;

import java.util.Stack;

/**
 * @Author ：snow
 * @Date   ：Created in 2020-05-06
 * @Description：
 * 有向图的基于深度优先搜索的顶点排序；前序、后序、逆后序
 * @Modified By：
 * @Version:
 */
public class DepthFirstSort {
    private boolean[] marked;
    private ArrayQueue<Integer> pre;    // 前序
    private ArrayQueue<Integer> post;   // 后序
    private Stack<Integer> reversePost; //后序

    public DepthFirstSort(DiGraph G){
        this.marked = new boolean[G.V()];
        pre = new ArrayQueue<Integer>();
        post = new ArrayQueue<Integer>();
        reversePost = new Stack<Integer>();

        for (int v = 0; v < G.V(); v ++){
            if ( !marked[v]) dfs(G, v);
        }
    }

    private void dfs(DiGraph G, int s){
        marked[s] = true;
        pre.enqueue(s);         // 前序排序就是在递归之前存储
        for (Integer w : G.adj(s)) {
            if (!marked[w]) dfs(G, w);
        }
        post.enqueue(s);
        reversePost.push(s);
    }

    public ArrayQueue<Integer> pre(){
        return this.pre;
    }
    public ArrayQueue<Integer> post() {
        return this.post;
    }

    public Stack<Integer> reversePost(){
        return this.reversePost;
    }
}
